package q148;

import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

/**
 * 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
 */
public class Solution {

    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        PriorityQueue<ListNode> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o.val));

        while (head != null) {
            pq.offer(head);
            head = head.next;
        }

        ListNode pre = pq.poll();
        pre.next = null;
        ListNode newHead = pre;
        while (!pq.isEmpty()) {
            ListNode cur = pq.poll();
            cur.next = null;
            pre.next = cur;
            pre = cur;
        }

        return newHead;
    }

}


class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
